Error detection and/or error correction codes are used for detecting and/or correcting errors in a signal. Forward error correction (FEC) is a system of error control for data transmission in which the sender adds redundant data to the transmitted data, which allows the receiver to detect and/or correct errors. The code rate of an FEC code is an indication of the portion of total information that is useful (i.e., non redundant). For example, if the code rate is x/y, for every x bits of useful information, the coder generates a total of y bits of data, of which (y-x) bits are redundant. Although higher redundancy may sometimes help in better error detection and/or correction, it may lower the code rate, thereby limiting the amount of useful information to be transmitted.
There exists several different types of FEC encoding and decoding techniques. Generalized (or multilevel) concatenated code (GCC) is a popular coding technique that is based on partitioning data into a number of subgroups or co-sets, and generating a plurality of inner codes and outer codes. The code class (referred to at the time as “generalized error locating codes” and confined to a linear partitioning scheme) was introduced by Blokh and Zyablov [V. Blokh, V. Zyablov, “Coding of Generalised Concatenated Codes,” Problems of Information Transmission, Volume 10 (1974), pp. 218-222] as a generalization of “Error Locating Codes”. Later Zinoviev [V. A. Zinoviev, “Generalized cascade codes.” Problemy Peredachi Informati, vol. 12, no. 1, pp. 5-15, 1976] found a more general description based on the partitioning of sets.
GCC is used for encoding data using a plurality of outer codes and inner codes, as will be explained in further detail later. GCC encoding involves partitioning of a code word of a finite length into different subgroups or co-sets, and partitioning each subgroup into further subgroups, and continuing the process until each subgroup or co-set includes only one single codeword. Before discussing various aspects of the GCC code, mathematical expression of the coding technique may be discussed. A plurality of linear codes are called “disjoint” if the linear codes have no common code word (except the all zero code word), and the dimension of the sum of the codes is given as the sum of the dimension of the addends. If each of a plurality of linear codes includes only one single codeword, then the plurality of linear codes are disjoint. Let C(pq; n, k, d) denote a linear code block of length n, dimension k, and a minimum hamming distance d over the Galois field GF(pq). As is well known in the art, for a fixed length m, the hamming distance is a metric on the vector space of the words of that length. Conventional GCC encoding is well known in the art, and a brief overview of GCC encoding will now be presented.
FIG. 1 illustrates a conventional GCC coding technique using an exemplary partition tree. Referring to FIG. 1, in various embodiments, a linear code B(0)(pq; nb, kb(0), db(0) may be partitioned into I number of subgroups or co-sets B1(1), B2(1), . . . , Bi(1), such that B(0)=Ui Bi(1). Such a partition may be denoted by B(0)/B(1) and I is the order of partition. The outer label, e.g., a1(0), denotes the coset B1(1). The subgroups or co-sets B1(0), B2(1), . . . , Bi(1) may collectively be referred as B(1). The number of subgroups or co-sets a code is partitioned into (e.g., in this case, I subgroups), for a given level, may be based at least in part on various factors, including but not limited to the dimension of the original code word, a parity check matrix used for partitioning, complexity involved in the partitioning, a type of GCC encoding used, etc.
Referring to FIG. 1, each of the subgroups B1(1), B2(1), . . . , Bi(1) in B(1) may be further partitioned into subgroups (in FIG. 1, only B1(1) is illustrated as further partitioned for the sake of clarity). This further partitioning may continue (illustrated by dotted lines) until each of the co-sets of the highest (i.e., the last) level (which is L in FIG. 1) includes only a single code word. Thus, in FIG. 1, the partitioning may continue until obtaining disjoint codes B1(L), B2(L), . . . , each including only one single code word, and resulting in an L-level partition chain B(1)/B(2)/. . . /B(L). A particular coset in the partition tree can be represented by a vector consists of coset labels along the partition branches starting from the tree root B(0). For example, the vector {a1(0), a1(1), . . . , a1(L−1)} represents the coset B1(L).
It should be noted that while only some of the intermediate co-sets are illustrated as being partitioned, all co-sets of all the intermediate level (i.e., 1, . . . , (L−1) levels) inner codes are partitioned. Accordingly, the inner code B(L) not only includes co-sets B1(L), B2(L), . . . , Bj(L) from partitioning B1(L−1) as illustrated, but also includes co-sets obtained from partitioning other co-sets of (L−1) level.
An L-level GCC code C consists of L outer codes A(l)(qma(l):na, ka(1), da(l)) and an inner code B(1)(q:nb, kb(1),db(1) that is partitioned into an L-level partition chain B(1)/B(2)/. . . /B(L+1). The subcodes of level L+1 consist of a single codeword only. The symbol ai(l) of the I-th outer code determines a subset of B(l)ai(1), ai(2), . . . , ai(l−1). Thus the symbols ai(l) of all outer codes together form the label (ai(1), . . . , ai(L)) of a unique codeword bi. The codeword of the GCC code consists of all the codewords bi,i=1, . . . , na.
The outer code can be related to the parity check matrix as follows. Let HB(L) be a parity check matrix of the inner code B(l) and ā(l) a codeword of the I-th outer code A(l), each codeword C of a GCC code in matrix form fulfillsā(l)=HB(l)/B(l+1)·C for all l=0, . . . , L−1.
In the above equation, notations are defined as
            H              B                  (          2          )                      =          [                                                  H                                                B                                      (                    1                    )                                                  /                                  B                                      (                    2                    )                                                                                                                          H                              B                                  (                  1                  )                                                                        ]        ,            …      ⁢                          ⁢      and      ⁢                          ⁢              H                  B                      (            L            )                                =                  [                                                                                                              ⁢                                  H                                                            B                                              (                                                  L                          -                          1                                                )                                                              /                                          B                                              (                        L                        )                                                                                                                                                    ⋮                                                                          H                                                      B                                          (                      1                      )                                                        /                                      B                                          (                      2                      )                                                                                                                                              H                                  B                                      (                    1                    )                                                                                      ]            .      
FIG. 2 illustrates an exemplary partition tree of a 3-level GCC code. Referring to FIG. 2, GCC coding may be used to partition the original code word B(0)(7,7,1). The 3-level GCC code may be constructed using inner codes B(0) (7,7,1)/ B(1)(7,6,2)/B(2)(7,3,4)/B(3)(7,0, ∞) and outer codes A(0) (2; 7,1,7), A(1)(23; 7,3,5), and A(2)(23; 7,5,3). The dimension of the inner codes decreases with the increase in its level, and the 3rd level code word B(3) includes only one single code word (i.e., of dimension 0). The hamming distances of the inner codes increases with an increase in the code level. For example, the 1st, 2nd, and 3rd level inner codes have a hamming distance of 2, 4, and infinity (each co-set of the 3rd level includes only one single, unique code word, resulting in an infinite hamming distance), respectively.
As will be readily appreciated by those skilled in the art, GCC introduces redundancies in the form of outer codes A(0), A(1), A(2), . . . , A(L−1) and/or the inner codes B(0). FIG. 3 illustrates an exemplary encoded data structure corresponding to the GCC partition tree of FIG. 2. The shaded portion of FIG. 3 corresponds to the redundancy bits for the outer codes A(0), A(1), A(2), while the white area may contain user information bits. As seen in FIG. 3, a large portion of the encoded data includes redundant bits generated by codes A(0), A(1), A(2). Although the higher redundancy may increase the correct power of the code, it may reduce the code rate.